package com.zdb.algorithm.prim;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class PrimAlgorithm {

    public static void main(String[] args) {
        Graph graph = MinTree.createGraph();
        graph.print();
        MinTree minTree = new MinTree();
        minTree.prim(graph, 'A');
    }
}

class MinTree {

    /**
     *
     * @param graph
     * @param vertex 出发顶点
     */
    public void prim(Graph graph, char vertex) {
        int vIndex = graph.getVertexIndex(vertex);

        // 已经访问过的设置为1
        int[] visited = new int[graph.getVertexSize()];

        List<String> minEdges = new ArrayList<>();

        // 设置当前顶点已经被访问了
        visited[vIndex] = 1;

        // 获取当前顶点有边可以访问的顶点，并得到最小权值的边对应的顶点
        int minWeight = Graph.NONE_DATA;
        int minWeightIdx = -1;
        int beginVertexIdx = 0;

        // 判断是否都被访问了
        while(!allVisited(visited)) {

            // 重新初始化值
            minWeight = Graph.NONE_DATA;
            minWeightIdx = -1;
            beginVertexIdx = 0;

            // 遍历所有已访问的顶点，寻找权值最小的边对应的顶点
            for (int visitedIndex = 0; visitedIndex < visited.length; visitedIndex++) {
                if(visited[visitedIndex] != 0) {
                    for (int i = 0; i < graph.weight[visitedIndex].length; i++) {
                        // 该点不能被访问过， 且权值小于当前最小值，则
                        if(visited[i] == 0 && graph.weight[visitedIndex][i] < minWeight) {
                            minWeight = graph.weight[visitedIndex][i];
                            minWeightIdx = i;
                            beginVertexIdx = visitedIndex;
                        }
                    }
                }
            }
            // 找到了最小路径
            if(minWeightIdx != -1) {
                visited[minWeightIdx] = 1;
                minEdges.add(graph.getVertexByIndex(beginVertexIdx)
                        + "-" + graph.getVertexByIndex(minWeightIdx) + "[" + minWeight + "]");
            }


        }
        
        System.out.println(minEdges);


    }

    /**
     * 判断是否都被访问了，即值都为1
     * @param visited
     * @return
     */
    private boolean allVisited(int[] visited) {

        for(int i : visited) {
            if(i == 0) {
                return false;
            }
        }
        return true;
    }

    public static Graph createGraph() {
        char[] vertexs = new char[]{'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        Graph graph = new Graph(vertexs);

        // 增加边
        graph.addEdge('A', 'C', 7);
        graph.addEdge('A', 'B', 5);
        graph.addEdge('A', 'G', 2);
        graph.addEdge('B', 'G', 3);
        graph.addEdge('B', 'D', 9);
        graph.addEdge('C', 'E', 8);
        graph.addEdge('E', 'G', 4);
        graph.addEdge('E', 'F', 5);
        graph.addEdge('F', 'G', 6);
        graph.addEdge('F', 'D', 4);

        return graph;
    }
}

class Graph {
    // 节点
    char[] vertexs;
    // 存放边及权重
    int[][] weight;
    // 顶点与vertexs中下标的对应关系
    Map<Character, Integer> vertex2index;

    public static final int NONE_DATA = 100;

    public Graph(char[] vertexs) {
        this.vertexs = vertexs;
        vertex2index = new HashMap<>();
        for (int i = 0; i < vertexs.length; i++) {
            vertex2index.put(vertexs[i], i);
        }
        weight = new int[vertexs.length][vertexs.length];
        for(int[] link : weight) {
            for (int i = 0; i < link.length; i++) {
                link[i] = NONE_DATA;
            }
        }
    }

    public int getVertexSize() {
        return vertexs.length;
    }

    /**
     * 增加边
     * @param a
     * @param b
     * @param weight
     */
    public void addEdge(char a, char b, int weight) {
        int aIdx = vertex2index.get(a);
        int bIdx = vertex2index.get(b);
        if(this.weight[aIdx][bIdx] == NONE_DATA) {
            this.weight[aIdx][bIdx] = weight;
            this.weight[bIdx][aIdx] = weight;
        }
    }

    /**
     * 获取顶点的下标
     * @param v
     * @return
     */
    public int getVertexIndex(char v) {
        return vertex2index.get(v);
    }

    /**
     * 通过下标获取顶点
     * @param index
     * @return
     */
    public char getVertexByIndex(int index) {
        return vertexs[index];
    }

    public void print() {
        for(int[] link : weight) {
            System.out.println(Arrays.toString(link));
        }
    }
}
